package com.melo;

import lombok.Data;

import java.util.Arrays;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 迪杰斯特拉算法: 已访问过的公交图
 * @date 2025-06-09
 */
@Data
public class DijkstraVisitedBusGraph {

    /**
     * 记录各个顶点是否访问过: 1表示访问过, 0未访问; 会动态更新
     */
    private int[] alreadyVisitedBusStationVertexArr;

    /**
     * 每个下标对应的值为前一个顶点下标, 会动态更新
     */
    private int[] preVisitedBusStationVertexArr;

    /**
     * 记录出发顶点到其他所有顶点的距离: 比如G为出发顶点, 就会记录G到其它顶点的距离, 会动态更新。求的最短距离就会存放到busStationDistinctArr
     */
    private int[] busStationDistanceArr;

    /**
     * @param vertexSize  顶点个数
     * @param vertexIndex 出发顶点对应的下标
     */
    public DijkstraVisitedBusGraph(int vertexSize, int vertexIndex) {
        this.alreadyVisitedBusStationVertexArr = new int[vertexSize];
        this.preVisitedBusStationVertexArr = new int[vertexSize];
        this.busStationDistanceArr = new int[vertexSize];
        // 初始化busStationDistinctArr
        Arrays.fill(busStationDistanceArr, 65535);
        // 设置出发顶点被访问过
        this.alreadyVisitedBusStationVertexArr[vertexIndex] = 1;
        // 设置出发顶点的访问距离为0
        this.busStationDistanceArr[vertexIndex] = 0;
    }

    // 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点)
    public int updateArr() {
        int minBusStationDistance = 65535, index = 0;
        for (int i = 0; i < alreadyVisitedBusStationVertexArr.length; i++) {
            if (alreadyVisitedBusStationVertexArr[i] == 0 && busStationDistanceArr[i] < minBusStationDistance) {
                minBusStationDistance = busStationDistanceArr[i];
                index = i;
            }
        }
        // 更新index顶点被访问过
        alreadyVisitedBusStationVertexArr[index] = 1;
        return index;
    }

    /**
     * 判断指定的顶点是否被访问过
     *
     * @param vertexIndex 顶点下标
     * @return true表示访问过, false未访问
     */
    public boolean checkVertexVisited(int vertexIndex) {
        return alreadyVisitedBusStationVertexArr[vertexIndex] == 1;
    }

    /**
     * 更新出发顶点到指定顶点的距离
     *
     * @param vertexIndex 指定顶点下标
     * @param distinct    距离
     */
    public void updateDistance(int vertexIndex, int distinct) {
        busStationDistanceArr[vertexIndex] = distinct;
    }

    /**
     * 功能: 更新pre这个顶点的前驱顶点为index顶点
     *
     * @param preVertexIndex 前驱顶点下标
     * @param index          当前顶点下标
     */
    public void updatePreVisitedBusStationVertex(int preVertexIndex, int index) {
        preVisitedBusStationVertexArr[preVertexIndex] = index;
    }

    /**
     * 返回出发顶点到index顶点的距离
     *
     * @param index 顶点下标
     * @return 距离
     */
    public int getDistance(int index) {
        return busStationDistanceArr[index];
    }

    // 打印最后的结果: 即输出alreadyVisitedBusStationVertexArr、preVisitedBusStationVertexArr、busStationDistanceArr三个数组
    public void show() {
        System.out.println("==========================");
        for (int i : alreadyVisitedBusStationVertexArr) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i : preVisitedBusStationVertexArr) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i : busStationDistanceArr) {
            System.out.print(i + " ");
        }
        System.out.println();
        // 方便查询最后的最短距离
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int count = 0;
        for (int i : busStationDistanceArr) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ") ");
            } else {
                System.out.println("N ");
            }
            count++;
        }
        System.out.println();
    }
}
